import java.util.Scanner;



public class BeadSort implements Runnable{

	public boolean abacusUpdated=false;
	public boolean finalUpdate=false;

	private int[] inArr;
	private int[][] abacus;

	public BeadSort()
	{
		inArr=new int[0];
	}

	public BeadSort(int[] in)
	{
		inArr=in;
	}
	
	public int[][] getAbacus()
	{
		abacusUpdated=false;
		return abacus;
	}
	
	public int[] getFinal()
	{
		finalUpdate=false;
		return inArr; //Yeah, it's the input as well as the final array.
	}

	public void run()
	{
		beadSort();
	}

	public void printArray(int[] arr)
	{
		System.out.print("[");
		for(int x=0; x<arr.length; x++)
		{
			if(x!=arr.length-1)
				System.out.print(arr[x]+", ");
			else
				System.out.print(arr[x]);
		}
		System.out.println("]");
	}

	public int largestElement(int[] arr)
	{
		int max=0;
		for(int x=0; x<arr.length; x++)
		{
			if (max<arr[x])
				max=arr[x];
		}
		return max;
	}

	public int[] beadCount()
	{
		int count=0;
		int[] arr=new int[abacus[0].length];

		for(int x=0; x<abacus[0].length; x++)
		{
			for(int y=0; y<abacus.length; y++)
			{
				if(abacus[y][x]==1)
					count++;
			}
			arr[x]=count;
			count=0;
		}
		return arr;
	}

	public void gravity(int[] arr)
	{
		int beadcount=0;

		for(int x=0; x<arr.length; x++)
		{
			if(arr[x]==1)
				beadcount++;
			arr[x]=0;
		}
		for(int x=arr.length-1; x>=0; x--)
		{
			if(beadcount>0)
			{
				arr[x]=1;
				beadcount--;
			}
		}
	}

	public void beadSort()
	{
		int large=largestElement(inArr);
		abacus=new int[large][inArr.length];

		printArray(inArr);
		System.out.println();


		for(int x=0; x<large; x++)
		{
			for(int y=0; y<inArr.length; y++)
			{
				if(x<inArr[y])
				{
					abacus[x][y]=1;
				}
			}
			printArray(abacus[x]);
		}

		abacusUpdated=true;
		while(abacusUpdated){}//Pause for dramatic effect...

		System.out.println();
		for(int x=0; x<abacus.length; x++)
		{
			gravity(abacus[x]);
			printArray(abacus[x]);
		}

		abacusUpdated=true;
		while(abacusUpdated){}//Pause for dramatic effect...

		inArr=beadCount();
		
		finalUpdate=true;
		while(finalUpdate){}//Drumroll, please!
		System.out.println();
		printArray(inArr);
	}


}

